Search for: All records

Researchers have modeled contagion processes on social networks for wide ranging applications, including spreading of epidemics, financial defaults, actions such as joining social media sites, and rumors. So, too, researchers have developed a host of intervention methods to control harmful contagions on networks; among these approaches are node and edge removal, separating network communities, altering contagion properties, and introducing a second competing contagion. In this work, minimum dominating sets are used to identify blocking nodes—nodes that do not contract a contagion and therefore also do not assist in transmitting it. A novel, generalized method that utilizes integer linear programming to determine exact minimum dominating sets (which is an NP-hard problem) has been developed for a subgraph of any social network for any combination of covering distance and coverage requirement. Three social networks are used to understand and evaluate (i) the method itself and (ii) the efficacy of the blocking nodes that the method produces to stop contagion spread.